Compute
\[\sum_{j = 0}^\infty \sum_{k = 0}^\infty 2^{-3k - j - (k + j)^2}.\]
Expanding, we get
\begin{align*}
3k + j + (k + j)^2 &= 3k + j + k^2 + 2kj + j^2 \\
&= k(k + 3) + 2kj + j(j + 1).
\end{align*}For each integer $k,$ either $k$ or $k + 3$ is even, so $k(k + 3)$ is always even.  Similarly, either $j$ or $j + 1$ is even, so $j(j + 1)$ is always even.  Thus, $3k + j + (k + j)^2$ is always even.

We claim that for any nonnegative integer $n,$ there exist unique nonnnegative integers $j$ and $k$ such that
\[3k  + j + (k + j)^2 = 2n.\]Let $a = k + j,$ so
\[3k + j + (k + j)^2 = 2k + (k + j) + (k + j)^2 = a^2 + a + 2k.\]For a fixed value of $a,$ $k$ can range from 0 to $a,$ so $a^2 + a + 2k$ takes on all even integers from $a^2 + a$ to $a^2 + a + 2a = a^2 + 3a.$

Furthermore, for $k + j = a + 1,$
\[3k + j + (k + j)^2 = (a + 1)^2 + (a + 1) + 2k = a^2 + 3a + 2 + 2k\]takes on all even integers from $a^2 + 3a + 2$ to $a^2 + 3a + 2 + 2(a + 1) = a^2 + 5a + 4,$ and so on.  Thus, for different values of $a = k + j,$ the possible values of $3k + j + (k + j)^2$ do not overlap, and it takes on all even integers exactly once.

Therefore,
\[\sum_{j = 0}^\infty \sum_{k = 0}^\infty 2^{-3k - j - (k + j)^2} = \sum_{i = 0}^\infty 2^{-2i} = \boxed{\frac{4}{3}}.\]